﻿#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include <iostream>
using namespace std;

namespace KVBS
{
	template<class K, class V>
	struct BSTNode
	{
		K _key;
		V _value;
		BSTNode<K, V>* _left;
		BSTNode<K, V>* _right;

		BSTNode(const K& key, const V& value)
			:_key(key)
			,_value(value)
			, _left(nullptr)
			, _right(nullptr)
		{}
	};
	template<class K, class V>
	class BSTree
	{
		typedef BSTNode<K, V> Node;
	public:
		bool Insert(const K& key, const V& value)
		{
			//无节点直接在根位置插入
			if (_root == nullptr)
			{
				Node* newnode = new Node(key, value);
				_root = newnode;
				return true;
			}
			Node* father = _root;
			Node* cur = _root;
			while (cur)
			{
				if (key < cur->_key)
				{
					father = cur;
					cur = cur->_left;
				}
				else if (key > cur->_key)
				{
					father = cur;
					cur = cur->_right;
				}
				else
				{
					return false;
				}
			}
			Node* newnode = new Node(key, value);
			if (key > father->_key)
			{
				father->_right = newnode;
			}
			else
			{
				father->_left = newnode;
			}
			return true;
		}
		Node* Find(const K& key)
		{
			Node* cur = _root;
			while (cur)
			{
				if (key < cur->_key)
				{
					cur = cur->_left;
				}
				else if (key > cur->_key)
				{
					cur = cur->_right;

				}
				else
				{
					return cur;
				}

			}
			return nullptr;
		}
		
		bool Erase(const K& key)
		{
			Node* father = nullptr;//记录上一个节点位置
			Node* cur = _root;//记录当前节点
			while (cur)//节点是否为空
			{
				//值比当前节点大往右走，小往左走
				if (key < cur->_key)
				{
					father = cur;
					cur = cur->_left;
				}
				else if (key > cur->_key)
				{
					father = cur;
					cur = cur->_right;

				}
				else//等于
				{
					if (cur->_left == nullptr)//判断左边是否为空，双空也可以用这个
					{
						if (cur == _root)//如果是根节点直接把根节点设置为右边第一个节点
						{
							_root = cur->_right;
						}
						else if (cur == father->_left)//不是根节点判断当前节点是父节点左子树还是右子树，是左子树直接就把当前节点的右节点给父节点左子树
						{
							father->_left = cur->_right;
						}
						else
						{
							father->_right = cur->_right;//是右子树直接就把当前节点的右节点给父节点右子树

						}
						delete cur;

					}
					else if (cur->_right == nullptr)
					{
						if (cur == _root)//如果是根节点直接把根节点设置为左边第一个节点
						{
							_root = cur->_left;
						}
						else if (cur == father->_left)//不是根节点判断当前节点是父节点左子树还是右子树，是左子树直接就把当前节点的左节点给父节点左子树
						{
							father->_left = cur->_left;
						}
						else
						{
							father->_right = cur->_left;//是右子树直接就把当前节点的左节点给父节点右子树
						}
						delete cur;
					}
					else//当前节点两边都不为空
					{
						Node* rep = cur->_left;//设置要替换当前节点的值
						Node* refather = cur;//设置替换值的父节点
						while (rep->_right)//找左子树的最右值
						{
							refather = rep;
							rep = rep->_right;
						}
						std::swap(cur->_key, rep->_key);//交换当前节点的和替换节点的值
						std::swap(cur->_value, rep->_value);//交换当前节点的和替换节点的值

						if (refather->_left == rep)//替换节点也就是要删除的节点把替换节点的左子树给替换节点的父节点
						{
							refather->_left = rep->_left;
						}
						else
						{
							refather->_right = rep->_left;
						}
						delete rep;
					}
					return true;
				}

			}
			return false;
		}
		void _InOrder(Node* root)
		{
			if (root == nullptr)
			{
				return;
			}
			_InOrder(root->_left);
			cout << root->_key << " : " << root->_value << endl;
			_InOrder(root->_right);
		}
		void InOrder()
		{
			_InOrder(_root);
		}
	private:
		Node* _root = nullptr;
	};

	
}






namespace KBS
{
	template<class K>
	struct BSTNode
	{
		K _key;
		BSTNode<K>* _left;
		BSTNode<K>* _right;

		BSTNode(const K& key)
			:_key(key)
			, _left(nullptr)
			, _right(nullptr)
		{}
	};


	template<class K>
	class BSTree
	{
		typedef BSTNode<K> Node;
	public:
		//插入节点
		bool Insert(const K& key)
		{
			//无节点直接在根位置插入
			if (_root == nullptr)
			{
				Node* newnode = new Node(key);
				_root = newnode;
				return true;
			}
			Node* father = _root;
			Node* cur = _root;
			while (cur)
			{
				if (key < cur->_key)
				{
					father = cur;
					cur = cur->_left;
				}
				else if (key > cur->_key)
				{
					father = cur;
					cur = cur->_right;
				}
				else
				{
					return false;
				}
			}
			Node* newnode = new Node(key);
			if (key > father->_key)
			{
				father->_right = newnode;
			}
			else
			{
				father->_left = newnode;
			}
			return true;
		}

		//找节点
		bool Find(const K& key)
		{
			Node* cur = _root;
			while (cur)
			{
				if (key < cur->_key)
				{
					cur = cur->_left;
				}
				else if (key > cur->_key)
				{
					cur = cur->_right;

				}
				else
				{
					return true;
				}

			}
			return false;
		}


		//删除节点
		bool Erase(const K& key)
		{
			Node* father = nullptr;//记录上一个节点位置
			Node* cur = _root;//记录当前节点
			while (cur)//节点是否为空
			{
				//值比当前节点大往右走，小往左走
				if (key < cur->_key)
				{
					father = cur;
					cur = cur->_left;
				}
				else if (key > cur->_key)
				{
					father = cur;
					cur = cur->_right;

				}
				else//等于
				{
					if (cur->_left == nullptr)//判断左边是否为空，双空也可以用这个
					{
						if (cur == _root)//如果是根节点直接把根节点设置为右边第一个节点
						{
							_root = cur->_right;
						}
						else if (cur == father->_left)//不是根节点判断当前节点是父节点左子树还是右子树，是左子树直接就把当前节点的右节点给父节点左子树
						{
							father->_left = cur->_right;
						}
						else
						{
							father->_right = cur->_right;//是右子树直接就把当前节点的右节点给父节点右子树

						}
						delete cur;

					}
					else if (cur->_right == nullptr)
					{
						if (cur == _root)//如果是根节点直接把根节点设置为左边第一个节点
						{
							_root = cur->_left;
						}
						else if (cur == father->_left)//不是根节点判断当前节点是父节点左子树还是右子树，是左子树直接就把当前节点的左节点给父节点左子树
						{
							father->_left = cur->_left;
						}
						else
						{
							father->_right = cur->_left;//是右子树直接就把当前节点的左节点给父节点右子树
						}
						delete cur;
					}
					else//当前节点两边都不为空
					{
						Node* rep = cur->_left;//设置要替换当前节点的值
						Node* refather = cur;//设置替换值的父节点
						while (rep->_right)//找左子树的最右值
						{
							refather = rep;
							rep = rep->_right;
						}
						std::swap(cur->_key, rep->_key);//交换当前节点的和替换节点的值
						if (refather->_left == rep)//替换节点也就是要删除的节点把替换节点的左子树给替换节点的父节点
						{
							refather->_left = rep->_left;
						}
						else
						{
							refather->_right = rep->_left;
						}
						delete rep;
					}
					return true;
				}
			}

			return false;

		}


		void copy(const BSTree<K>& x)
		{
			_Destroy(_root);
			_copy(_root, x._root);
		}


		void _copy(Node*& mroot, Node* oroot)
		{
			if (oroot == nullptr)
			{
				return;
			}
			Node* newnode = new Node(oroot->_key);
			mroot = newnode;
			_copy(mroot->_left, oroot->_left);
			_copy(mroot->_right, oroot->_right);
		}

		void InOrder()
		{
			_InOrder(_root);
			cout << endl;
		}


		void _InOrder(Node* root)
		{
			if (root == nullptr)
			{
				return;
			}
			_InOrder(root->_left);
			cout << root->_key << ' ';
			_InOrder(root->_right);
		}

		~BSTree()
		{
			_Destroy(_root);
			_root = nullptr;
		}
		void _Destroy(Node* root)
		{
			if (root == nullptr)
			{
				return;
			}
			_Destroy(root->_left);
			_Destroy(root->_right);
			delete root;
		}

	private:
		Node* _root = nullptr;
	};
}